package com.zhn;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 给定一个二叉树，找出其最小深度。
 *
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 *
 * 说明：叶子节点是指没有子节点的节点。
 */

public class MinDepth {
    public int minDepth(TreeNode root) {
        if(root == null)return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.add(root);
        int count = 0;
        while(!que.isEmpty()){
            count++;
            int len = que.size();
            while(len-->0){
                TreeNode poll = que.poll();
                //左右两个节点都为空，说明为叶子节点，当前为最小深度
                if(poll.left == null && poll.right == null){
                    return count;
                }
                if(poll.left != null) que.add(poll.left);
                if(poll.right != null)que.add(poll.right);
            }
        }
        return count;
    }
}
